/**
 * @Author Fizz Pu
 * @Date 2020/12/14 下午6:21
 * @Version 1.0
 * 失之毫厘，缪之千里！
 */


class LeeOffer68 {

    // 1302ms
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        int pLoc = getLocation(root, p);
        int qLoc = getLocation(root, q);

        if(qLoc == 0 ){return q;}
        if(pLoc == 0){return p;}
        if(qLoc != pLoc) {
            return root;
        }

        if(qLoc == 1 && pLoc == 1){
            return lowestCommonAncestor(root.left,p,q);
        }

        return lowestCommonAncestor(root.right, p, q);
    }

    /**
     *
     * @param root
     * @param p
     * @return p == root 返回0; p 在左子树中, 返回1; p在右子树中, 返回2
     */
    private int getLocation(TreeNode root, TreeNode p){
        if( p.val == root.val) return 0;
        if(contain(root.right, p))return 2;
        return 1;
    }

    private boolean contain(TreeNode root , TreeNode p) {
        if (root != null) {
            if (root.val == p.val) {
                return true;
            } else {
                return contain(root.left, p) || contain(root.right, p);
            }
        }
        return false;
    }
}



